{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Palindrome With Fixed Length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到指定长度的回文数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>queries</code>&nbsp;和一个 <strong>正</strong>&nbsp;整数&nbsp;<code>intLength</code>&nbsp;，请你返回一个数组&nbsp;<code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code> 是长度为&nbsp;<code>intLength</code>&nbsp;的&nbsp;<strong>正回文数</strong> 中第<em>&nbsp;</em><code>queries[i]</code>&nbsp;小的数字，如果不存在这样的回文数，则为 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>回文数</strong> 指的是从前往后和从后往前读一模一样的数字。回文数不能有前导 0 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>queries = [1,2,3,4,5,90], intLength = 3\n",
    "<b>输出：</b>[101,111,121,131,141,999]\n",
    "<strong>解释：</strong>\n",
    "长度为 3 的最小回文数依次是：\n",
    "101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...\n",
    "第 90 个长度为 3 的回文数是 999 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>queries = [2,4,6], intLength = 4\n",
    "<b>输出：</b>[1111,1331,1551]\n",
    "<strong>解释：</strong>\n",
    "长度为 4 的前 6 个回文数是：\n",
    "1001, 1111, 1221, 1331, 1441 和 1551 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= intLength&nbsp;&lt;= 15</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-palindrome-with-fixed-length](https://leetcode.cn/problems/find-palindrome-with-fixed-length/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-palindrome-with-fixed-length](https://leetcode.cn/problems/find-palindrome-with-fixed-length/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,90]\\n3', '[2,4,6]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        # length 3, 90th, 10 + 90 - 1 = 999\n",
    "        # length 4, 90th, 10 + 90 - 1 = 9999\n",
    "        res = []\n",
    "        is_odd = True\n",
    "        if intLength % 2 == 0:\n",
    "            is_odd = False\n",
    "        intLength = (intLength + 1) // 2\n",
    "        base_num = 10 ** (intLength - 1)\n",
    "        max_query = base_num * 9\n",
    "        for q in queries:\n",
    "            if q <= max_query:\n",
    "                first_half = str(base_num + q - 1)\n",
    "                if is_odd:\n",
    "                    res.append(int(first_half[:-1] + first_half[::-1]))\n",
    "                else:\n",
    "                    res.append(int(first_half + first_half[::-1]))\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        queries_length = len(queries)\n",
    "        answer_list = [-1] * queries_length\n",
    "        max_query = 10 ** ((intLength - 1) // 2) * 9\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for index in range(queries_length):\n",
    "            searchPalindrome(max_query, answer_list, base, intLength,queries[index], index)\n",
    "        return answer_list\n",
    "\n",
    "def searchPalindrome(max_query, answer_list, base, intLength, query, index):\n",
    "    if query <= max_query:\n",
    "        palindrome_left = base + query - 1\n",
    "        palindrome_left_str = str(palindrome_left)\n",
    "        palindrome_left_str_length = len(palindrome_left_str)\n",
    "        if intLength % 2:\n",
    "            palindrome_str = palindrome_left_str + palindrome_left_str[-2:-palindrome_left_str_length - 1:-1]\n",
    "        else:\n",
    "            palindrome_str = palindrome_left_str + palindrome_left_str[::-1]\n",
    "        answer_list[index] = int(palindrome_str)\n",
    "   \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)  # 初始化返回结果\n",
    "        base = 10 ** ((intLength - 1) // 2)  # 计算基数\n",
    "        \n",
    "        for i, q in enumerate(queries):  # 遍历每一个查询\n",
    "            if q <= 9 * base:  # 判断是否可能生成一个长度为intLength的回文数\n",
    "                # 生成回文数的前半部分\n",
    "                s = str(base + q - 1)\n",
    "                # 根据intLength生成完整的回文数\n",
    "                s += s[-2::-1] if intLength % 2 else s[::-1]\n",
    "                ans[i] = int(s)  # 保存结果\n",
    "        return ans  # 返回结果\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        length = 9*10**((intLength-1)//2)\n",
    "        res = [-1]*len(queries)\n",
    "        if intLength %2 == 0:\n",
    "            start = 10**(intLength//2-1)\n",
    "        else:\n",
    "            start = 10**(intLength//2)\n",
    "        for i in range(len(queries)):\n",
    "            num = queries[i]\n",
    "            if num > length:\n",
    "                continue\n",
    "            temp = str(start+num-1)\n",
    "            if intLength %2 == 0:\n",
    "                res[i] = int(temp+temp[::-1])\n",
    "            else:\n",
    "                res[i] = int(temp[:-1]+temp[-1]+temp[:-1][::-1])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        for i, q in enumerate(queries):\n",
    "            base = 10 ** ((intLength - 1) // 2)\n",
    "            left = str(base + q - 1)\n",
    "            if q <= 9 * base:\n",
    "                right = left[::-1]\n",
    "                if intLength % 2:\n",
    "                    right = right[1:]\n",
    "                ans[i] = int(left + right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for i, q in enumerate(queries):\n",
    "            if (q > 9 * base): continue\n",
    "            s = str(base + q - 1)\n",
    "            s += s[-2::-1] if intLength % 2 else s[::-1]\n",
    "            ans[i] = int(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for i, q in enumerate(queries):\n",
    "            if q <= 9 * base:\n",
    "                s = str(base + q - 1)  # 回文数左半部分\n",
    "                s += s[-2::-1] if intLength % 2 != 0 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1)//2\n",
    "        start = 10 ** (l - 1) -1\n",
    "        limit = 10 ** l - 1\n",
    "        res = []\n",
    "        def recover(num:int) ->int:\n",
    "            if intLength %2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1]+str(num)[::-1])\n",
    "            \n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        base = 10 ** ((intLength-1) // 2)\n",
    "        for i, qi in enumerate(queries):\n",
    "            if qi + base > base * 10:\n",
    "                continue\n",
    "            pre = base + qi - 1\n",
    "            if intLength % 2 == 0:\n",
    "                ans[i] = int(str(pre) + str(pre)[::-1])\n",
    "            else:\n",
    "                ans[i] = int(str(pre) + str(pre)[::-1][1:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        leftN = (intLength + 1)>>1\n",
    "        odd = intLength & 1\n",
    "        start = int('1' + '0'*(leftN-1))\n",
    "        _max = int('9'*leftN)\n",
    "        result = [-1]*len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            q += start - 1\n",
    "            if q <= _max:\n",
    "                q = str(q)\n",
    "                result[i] = int(q + q[-2 if odd else None::-1])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for i, q in enumerate(queries):\n",
    "            if q <= 9 * base:\n",
    "                s = str(base + q - 1)  # 回文数左半部分\n",
    "                s += s[-2::-1] if intLength % 2 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        # g[i]表示长度为i的回文字串的集合为g[i]\n",
    "        ans = [-1]*len(queries)\n",
    "        base = 10**((intLength-1)//2)\n",
    "        for i,q in enumerate(queries):\n",
    "            if q <= 9*base:\n",
    "                s = str(base+q-1)\n",
    "                s += s[-2::-1] if intLength%2 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for i, q in enumerate(queries):\n",
    "            if q <= 9 * base:\n",
    "                s = str(base + q - 1)  # 回文数左半部分\n",
    "                s += s[-2::-1] if intLength % 2 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for i, q in enumerate(queries):\n",
    "            if q <= 9 * base:\n",
    "                s = str(base + q - 1)  # 回文数左半部分\n",
    "                s += s[-2::-1] if intLength % 2 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        def is_palindrome(num: int) -> bool:\n",
    "            num_str = str(num)\n",
    "            return num_str == num_str[::-1]\n",
    "\n",
    "        def generate_kth_palindrome(k: int, length: int) -> int:\n",
    "            if length == 1:\n",
    "                if 1 <= k <= 9:\n",
    "                    return k\n",
    "                else:\n",
    "                    return -1\n",
    "            half_length = (length + 1) // 2\n",
    "            max_half = 10**(half_length) - 1\n",
    "            min_half = 10**(half_length - 1)\n",
    "            total_palindromes = max_half - min_half + 1\n",
    "            if k > total_palindromes:\n",
    "                return -1\n",
    "            half_num = min_half + k - 1\n",
    "            left_half = str(half_num)\n",
    "            right_half = left_half[::-1]\n",
    "            if length % 2 == 1:\n",
    "                right_half = right_half[1:]\n",
    "            palindrome = int(left_half + right_half)\n",
    "            return palindrome\n",
    "\n",
    "        answer = []\n",
    "        for query in queries:\n",
    "            answer.append(generate_kth_palindrome(query, intLength))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   \n",
    "        start = 10 ** (l - 1) - 1   \n",
    "        limit = 10 ** l - 1\n",
    "        res = []\n",
    "\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "\n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                # 不存在\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res\n",
    "\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "\t\tmaximum=10**((intLength+1)//2)-1\n",
    "\t\tminimum=10**((intLength-1)//2)\n",
    "\t\tans=[]\n",
    "\t\todd=intLength%2\n",
    "\t\tfor q in queries:\n",
    "\t\t\tres=minimum+q-1\n",
    "\t\t\tif res<=maximum:\n",
    "\t\t\t\tres=str(res)\n",
    "\t\t\t\tres+=res[-2::-1] if odd else res[::-1]\n",
    "\t\t\t\tans.append(int(res))\n",
    "\t\t\telse:\n",
    "\t\t\t\tans.append(-1)\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for i, q in enumerate(queries):\n",
    "            if q <= 9 * base:\n",
    "                s = str(base + q - 1)  # 回文数左半部分\n",
    "                s += s[-2::-1] if intLength % 2 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for i, q in enumerate(queries):\n",
    "            if q <= 9 * base:\n",
    "                s = str(base + q - 1)  # 回文数左半部分\n",
    "                s += s[-2::-1] if intLength % 2 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "左半：10... 递增\n",
    "右半: 反转，\n",
    "'''\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        base = 10 ** ((intLength - 1) // 2)\n",
    "        for i, q in enumerate(queries):\n",
    "            if q <= 9 * base:\n",
    "                s = str(base + q - 1)  # 回文数左半部分\n",
    "                s += s[-2::-1] if intLength % 2 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        base = 10**((intLength-1)//2)\n",
    "        ans = [-1]*(len(queries))\n",
    "        for i,q in enumerate(queries):\n",
    "            if q <= 9*base:\n",
    "                s = str(base+q-1)\n",
    "                s += s[-2::-1] if intLength%2 else s[::-1]\n",
    "                ans[i] = int(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        def hw(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "            \n",
    "        half = (intLength + 1) // 2\n",
    "        start = 10 ** (half - 1)\n",
    "        end = 10 ** half\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            if q > end - start:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(hw(start + q - 1))\n",
    "        return ans\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        for i, q in enumerate(queries):\n",
    "            base = 10 ** ((intLength - 1) // 2)\n",
    "            left = str(base + q - 1)\n",
    "            if len(left) > len(str(base)):\n",
    "                continue\n",
    "            right = left[::-1]\n",
    "            if intLength % 2:\n",
    "                right = right[1:]\n",
    "            ans[i] = int(left + right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans=[-1]*len(queries)\n",
    "        base=10**((intLength-1)//2)\n",
    "        for i,q in enumerate(queries):\n",
    "            if q<=9*base:\n",
    "                s=str(base+q-1)\n",
    "                s+=s[-2::-1] if intLength%2 else s[::-1]\n",
    "                ans[i]=int(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        half_length = (intLength + 1) // 2\n",
    "        rem_length = intLength - half_length\n",
    "        smallest, largest = 10 ** (half_length - 1), 10 ** half_length - 1\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            target = smallest + q - 1\n",
    "            if target > largest:\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            target = list(str(target))\n",
    "            for i in range(rem_length-1, -1, -1):\n",
    "                target.append(target[i])\n",
    "            res.append(int(\"\".join(target)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        min_num = int(math.pow(10,(intLength-1)//2))\n",
    "        max_num = int(math.pow(10,(intLength+1)//2)-1)\n",
    "        list1 = []\n",
    "        for i in queries:\n",
    "            if intLength % 2 == 0:\n",
    "                first = (min_num+i)-1\n",
    "                min_first = str(first)+str(first)[::-1]\n",
    "                max_last = str(max_num)+str(max_num)[::-1]\n",
    "                if int(min_first) <= int(max_last):\n",
    "                    list1.append(int(min_first))\n",
    "                else:\n",
    "                    list1.append(-1)\n",
    "            else:\n",
    "                first = (min_num + i)-1\n",
    "                min_first = str(first) + str(first)[::-1][1:]\n",
    "                max_last = str(max_num) + str(max_num)[::-1][1:]\n",
    "                if int(min_first) <= int(max_last):\n",
    "                    list1.append(int(min_first))\n",
    "                else:\n",
    "                    list1.append(-1)\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        half,base = (intLength+1) // 2,10** ((intLength + 1) // 2 - 1)\n",
    "        return [(func:=lambda q:-1 if len(left:= str(base + q - 1)) > half else int(left + ''.join(left[i] for i in range(len(left) - 1 - intLength % 2, -1, -1))))(q) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        n = (intLength  - 1)//2\n",
    "        base = 10**n\n",
    "        ans = []\n",
    "        for num in queries:\n",
    "            if num > 9 *base:\n",
    "                ans.append(-1)\n",
    "                continue\n",
    "            else:\n",
    "                num_str = str(base + num -1)\n",
    "                num_str2 = num_str[:-1][::-1] if intLength %2 else num_str[::-1]\n",
    "                tmp = num_str + num_str2\n",
    "            ans.append(int(tmp))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "        for query in queries:\n",
    "            temp=recover(start + query)\n",
    "            if len(str(temp))>intLength:\n",
    "                res.append(-1)\n",
    "            else :\n",
    "                res.append(recover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1)//2\n",
    "        start = 10 ** (l - 1) -1\n",
    "        limit = 10 ** l - 1\n",
    "        res = []\n",
    "        def recover(num:int) ->int:\n",
    "            if intLength %2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1]+str(num)[::-1])\n",
    "            \n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        limit = 10 ** l - 1   # l 位无前导零整数的上界\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "        for query in queries:\n",
    "            temp=recover(start + query)\n",
    "            if len(str(temp))>intLength:\n",
    "                res.append(-1)\n",
    "            else :\n",
    "                res.append(recover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        if intLength == 1:\n",
    "            return [(0+i) if i < 10 else -1 for i in queries]\n",
    "        # if intLength % 2 == 0:\n",
    "        #     k = intLength // 2\n",
    "        # else:\n",
    "        #     k = intLength // 2 + 1\n",
    "        k = ceil(intLength / 2)\n",
    "        res = []\n",
    "        le = intLength - k\n",
    "        for num in queries:\n",
    "            pre = str(10**(k-1)+num-1)\n",
    "            las = pre[:le][::-1]\n",
    "            nub = int(pre+las)\n",
    "            if nub < 10**intLength:\n",
    "                res.append(nub)\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        min_num = math.pow(10,math.floor((intLength-1)/2))\n",
    "        max_num = math.pow(10, math.floor((intLength+1)/2)) -1\n",
    "        result = []\n",
    "        for i in queries:\n",
    "            temp = int(i-1 + min_num)\n",
    "            flag = intLength %2 == 0\n",
    "            if temp <= max_num and flag:\n",
    "                result.append(int(str(temp)+str(temp)[::-1]))\n",
    "            elif temp <= max_num and not flag:\n",
    "                result.append(int(str(temp)+str(temp)[::-1][1:]))\n",
    "            else:\n",
    "                result.append(-1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        limit = 10 ** l - 1   # l 位无前导零整数的上界\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "\n",
    "        # 依次处理询问\n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                # 不存在\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        n = (intLength + 1) // 2\n",
    "        mn = 10 ** (n - 1) #1, 10, 100\n",
    "        mx = 10 ** (n) - 1 #9, 99, 999\n",
    "        ans = []\n",
    "        for x in queries:\n",
    "            if mn + x - 1 <= mx:\n",
    "                s = str(mn + x - 1)\n",
    "                ans.append(int(s + s[::-1][intLength%2:]))\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        limit = 10 ** l - 1   # l 位无前导零整数的上界\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "\n",
    "        # 依次处理询问\n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                # 不存在\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        if intLength == 1:\n",
    "            return [(0+i) if i < 10 else -1 for i in queries]\n",
    "        # if intLength % 2 == 0:\n",
    "        #     k = intLength // 2\n",
    "        # else:\n",
    "        #     k = intLength // 2 + 1\n",
    "        k = ceil(intLength / 2)\n",
    "        res = []\n",
    "        le = intLength - k\n",
    "        for num in queries:\n",
    "            pre = str(10**(k-1)+num-1)\n",
    "            las = pre[:le][::-1]\n",
    "            nub = int(pre+las)\n",
    "            if nub < 10**intLength:\n",
    "                res.append(nub)\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        half = math.ceil(intLength / 2)\n",
    "        ans = []\n",
    "        l = 10 ** (half - 1)\n",
    "        r = 10 ** half\n",
    "        for q in queries:\n",
    "            if l + q > r:\n",
    "                ans.append(-1)\n",
    "                continue\n",
    "            num = l + q - 1\n",
    "            s = str(num)\n",
    "            if intLength % 2 == 0:\n",
    "                cur = int(s + s[::-1])\n",
    "            else:\n",
    "                cur = int(s + s[::-1][1:])\n",
    "            ans.append(cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        if intLength == 1:\n",
    "            return [(0+i) if i < 10 else -1 for i in queries]\n",
    "        if intLength % 2 == 0:\n",
    "            k = intLength // 2\n",
    "        else:\n",
    "            k = intLength // 2 + 1\n",
    "        res = []\n",
    "        le = intLength - k\n",
    "        for num in queries:\n",
    "            pre = str(10**(k-1)+num-1)\n",
    "            las = pre[:le][::-1]\n",
    "            nub = int(pre+las)\n",
    "            if nub < 10**intLength:\n",
    "                res.append(nub)\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        k = (intLength + 1 )// 2\n",
    "        half = []\n",
    "\n",
    "        for q in queries:\n",
    "            start = 10 ** (k - 1)\n",
    "            end = 10 ** k - 1\n",
    "            maxq = end - start + 1\n",
    "            if q > maxq:\n",
    "                half.append(-1)\n",
    "            else:\n",
    "                half.append(start + q - 1)\n",
    "        \n",
    "        ans = []\n",
    "        # 偶数情况\n",
    "\n",
    "        if intLength % 2 == 0:\n",
    "            ans = [int(str(item) + str(item)[::-1]) if item != -1 else -1 for item in half]\n",
    "        else:\n",
    "            ans = [int(str(item) + str(item)[:-1][::-1]) if item != -1 else -1 for item in half]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = [1] * 16\n",
    "MX[1] = 9\n",
    "for i in range(2,9):\n",
    "    MX[i] = 9 * (MX[i-1]+10**(i-2))\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            q -= 1\n",
    "            ans = ''\n",
    "            l = (intLength+1)//2\n",
    "            if q >= MX[l]:res.append(-1)\n",
    "            else:\n",
    "                for i in range(l-1,-1,-1):\n",
    "                    ans += chr(ord('1' if i == l-1 else '0') + q//(MX[i+1]//9))\n",
    "                    q %= (MX[i+1]//9)\n",
    "                if intLength % 2:\n",
    "                    ans = ans + (ans[:-1][::-1])\n",
    "                else:\n",
    "                    ans = ans + ans[::-1]\n",
    "                res.append(int(ans))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        def generate_kth_palindrome(k: int, length: int) -> int:\n",
    "            if length == 1:\n",
    "                if 1 <= k <= 9:\n",
    "                    return k\n",
    "                else:\n",
    "                    return -1\n",
    "            half_length = (length + 1) // 2\n",
    "            max_half = 10**(half_length) - 1\n",
    "            min_half = 10**(half_length - 1)\n",
    "            total_palindromes = max_half - min_half + 1\n",
    "            if k > total_palindromes:\n",
    "                return -1\n",
    "            left_half = min_half + k - 1\n",
    "            right_half = str(left_half)[::-1]\n",
    "            if length % 2 == 1:\n",
    "                right_half = right_half[1:]\n",
    "            return int(str(left_half) + right_half)\n",
    "\n",
    "        answer = []\n",
    "        for query in queries:\n",
    "            answer.append(generate_kth_palindrome(query, intLength))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        min_num = int(math.pow(10,(intLength-1)//2))\n",
    "        max_num = int(math.pow(10,(intLength+1)//2)-1)\n",
    "        list1 = []\n",
    "        for i in queries:\n",
    "            first = (min_num + i) - 1\n",
    "            if intLength % 2 == 0:\n",
    "                min_first = str(first)+str(first)[::-1]\n",
    "                max_last = str(max_num)+str(max_num)[::-1]\n",
    "            else:\n",
    "                min_first = str(first) + str(first)[::-1][1:]\n",
    "                max_last = str(max_num) + str(max_num)[::-1][1:]\n",
    "            if int(min_first) <= int(max_last):\n",
    "                list1.append(int(min_first))\n",
    "            else:\n",
    "                list1.append(-1)\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        limit = 10 ** l - 1   # l 位无前导零整数的上界\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "\n",
    "        # 依次处理询问\n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                # 不存在\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], L: int) -> List[int]:\n",
    "        ans = []\n",
    "        if L == 1:\n",
    "            for q in queries:\n",
    "                if q > 9:\n",
    "                    ans.append(-1)\n",
    "                else:\n",
    "                    ans.append(q)\n",
    "            return ans\n",
    "        if L & 1:\n",
    "            left = (L - 1) // 2\n",
    "            limit = 9 * pow(10,left - 1) * 10\n",
    "        else:\n",
    "            left = L // 2\n",
    "            limit = 9 * pow(10,left - 1)\n",
    "        init = pow(10,left - 1)\n",
    "        for q in queries:\n",
    "            if q > limit:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                if L & 1:\n",
    "                    cnt = q // 10\n",
    "                    lf = q % 10\n",
    "                    if lf == 0:\n",
    "                        num = str(init + cnt - 1) + '9' + str(init + cnt - 1)[::-1]\n",
    "                    else:\n",
    "                        num = str(init + cnt) + str(lf - 1) + str(init + cnt)[::-1]\n",
    "                else:\n",
    "                    num = str(init + q - 1) + str(init + q - 1)[::-1]\n",
    "                ans.append(int(num))\n",
    "                    \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2\n",
    "        start = 10 **(l - 1) -1\n",
    "        limit = 10 ** (l) - 1\n",
    "        res = []\n",
    "        def rcover(num:int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "        \n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(rcover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = []\n",
    "        intLength2 = (intLength+1)//2\n",
    "        for i in queries:\n",
    "            ta = str(1*10**(intLength2-1)+i-1)\n",
    "            if len(ta)>intLength2:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(int(ta+ta[:intLength2-intLength%2][::-1]))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        midL=(intLength+1)//2\n",
    "        res=[]\n",
    "        for num in queries:\n",
    "            if num>10**midL-10**(midL-1):\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            tmp=10**(midL-1)+num-1\n",
    "            tmp=str(tmp)\n",
    "            if intLength%2:\n",
    "                tmp=tmp+tmp[-2::-1]\n",
    "                res.append(int(tmp))\n",
    "            else:\n",
    "                tmp=tmp+tmp[::-1]\n",
    "                res.append(int(tmp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        def generate_kth_palindrome(k: int, length: int) -> int:\n",
    "            if length == 1:\n",
    "                if k <= 9:\n",
    "                    return k\n",
    "                else:\n",
    "                    return -1\n",
    "            half_length = (length + 1) // 2\n",
    "            start = 10**(half_length - 1)\n",
    "            end = 10**half_length\n",
    "            total_palindromes = end - start\n",
    "            if k > total_palindromes:\n",
    "                return -1\n",
    "            num = start + k - 1\n",
    "            left_half = str(num)\n",
    "            right_half = left_half[::-1]\n",
    "            if length % 2 == 1:\n",
    "                right_half = right_half[1:]\n",
    "            palindrome = int(left_half + right_half)\n",
    "            return palindrome\n",
    "\n",
    "        answer = []\n",
    "        for query in queries:\n",
    "            kth_palindrome = generate_kth_palindrome(query, intLength)\n",
    "            answer.append(kth_palindrome)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        if intLength == 1:\n",
    "            return [(0+i) if i < 10 else -1 for i in queries]\n",
    "        # if intLength % 2 == 0:\n",
    "        #     k = intLength // 2\n",
    "        # else:\n",
    "        #     k = intLength // 2 + 1\n",
    "        k = ceil(intLength / 2)\n",
    "        res = []\n",
    "        le = intLength - k\n",
    "        for num in queries:\n",
    "            pre = str(10**(k-1)+num-1)\n",
    "            las = pre[:le][::-1]\n",
    "            nub = int(pre+las)\n",
    "            if nub < 10**intLength:\n",
    "                res.append(nub)\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        limit = 10 ** l - 1   # l 位无前导零整数的上界\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "\n",
    "        # 依次处理询问\n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                # 不存在\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        limit = 10 ** l - 1   # l 位无前导零整数的上界\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "\n",
    "        # 依次处理询问\n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                # 不存在\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        min_num = int(math.pow(10,(intLength-1)//2))\n",
    "        max_num = int(math.pow(10,(intLength+1)//2)-1)\n",
    "        list1 = []\n",
    "        for i in queries:\n",
    "            first = (min_num + i) - 1\n",
    "            if intLength % 2 == 0:\n",
    "                min_first = str(first)+str(first)[::-1]\n",
    "                max_last = str(max_num)+str(max_num)[::-1]\n",
    "            else:\n",
    "                min_first = str(first) + str(first)[::-1][1:]\n",
    "                max_last = str(max_num) + str(max_num)[::-1][1:]\n",
    "            if int(min_first) <= int(max_last):\n",
    "                list1.append(int(min_first))\n",
    "            else:\n",
    "                list1.append(-1)\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = []\n",
    "        intLength2 = (intLength+1)//2\n",
    "        for i in queries:\n",
    "            ta = str(1*10**(intLength2-1)+i-1)\n",
    "            if len(ta)>intLength2:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(int(ta+ta[:intLength2-intLength%2][::-1]))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        limit = 10 ** l - 1   # l 位无前导零整数的上界\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "\n",
    "        # 依次处理询问\n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                # 不存在\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        l = (intLength + 1) // 2   # 可以唯一确定回文数的前半部分的长度\n",
    "        start = 10 ** (l - 1) - 1   # start + k 即为第 k 个 l 位无前导零整数\n",
    "        limit = 10 ** l - 1   # l 位无前导零整数的上界\n",
    "        res = []\n",
    "        # 将前半部分恢复为对应的回文数\n",
    "        def recover(num: int) -> int:\n",
    "            if intLength % 2 == 0:\n",
    "                return int(str(num) + str(num)[::-1])\n",
    "            else:\n",
    "                return int(str(num)[:-1] + str(num)[::-1])\n",
    "\n",
    "        # 依次处理询问\n",
    "        for query in queries:\n",
    "            if start + query > limit:\n",
    "                # 不存在\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            res.append(recover(start + query))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        ans = []\n",
    "        intLength2 = (intLength+1)//2\n",
    "        for i in queries:\n",
    "            ta = str(1*10**(intLength2-1)+i-1)\n",
    "            if len(ta)>intLength2:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(int(ta+ta[:intLength2-intLength%2][::-1]))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        if intLength == 1:\n",
    "            return [(0+i) if i < 10 else -1 for i in queries]\n",
    "        if intLength % 2 == 0:\n",
    "            k = intLength // 2\n",
    "        else:\n",
    "            k = intLength // 2 + 1\n",
    "        res = []\n",
    "        le = intLength - k\n",
    "        for num in queries:\n",
    "            pre = str(10**(k-1)+num-1)\n",
    "            las = pre[:le][::-1]\n",
    "            nub = int(pre+las)\n",
    "            if nub < 10**intLength:\n",
    "                res.append(nub)\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        if(intLength % 2 == 0):\n",
    "            l = intLength // 2 - 1\n",
    "            flag = True\n",
    "        else:\n",
    "            l = intLength // 2\n",
    "            flag = False\n",
    "        start = 10**l \n",
    "        result = []\n",
    "        for q in queries:\n",
    "            if(start + q - 1 >= start*10):\n",
    "                result.append(-1)\n",
    "            else:\n",
    "                halfs = str(start + q - 1)\n",
    "                if(flag):\n",
    "                    result.append(int(halfs+halfs[::-1]))\n",
    "                else:\n",
    "                    result.append(int(halfs+halfs[:-1][::-1]))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\r\n",
    "\r\n",
    "        if intLength == 1:\r\n",
    "            res = []\r\n",
    "            for q in queries:\r\n",
    "                res.append(q if q <= 9 else -1)\r\n",
    "            return res \r\n",
    "\r\n",
    "        path = [\"\"] * intLength\r\n",
    "\r\n",
    "        res = \"\"\r\n",
    "        ans = []\r\n",
    "        def dfs(i:int, left: int):\r\n",
    "            nonlocal res \r\n",
    "            if i == (intLength - 1) // 2  + 1 :\r\n",
    "                res =  \"\".join(path)    \r\n",
    "                return     \r\n",
    "            cnt = pow(10, (intLength + 1) // 2 - i - 1)\r\n",
    "            low = 1 if i == 0 else 0\r\n",
    "            for x in range(low, 10):\r\n",
    "                if left - cnt > 0:\r\n",
    "                    left -= cnt\r\n",
    "                    continue\r\n",
    "                else:\r\n",
    "                    path[i] = path[len(path) - i - 1] = str(x)\r\n",
    "                    dfs(i + 1, left)\r\n",
    "                    return\r\n",
    "        mx = pow(10, (intLength + 1) // 2 - 1) * 9\r\n",
    "        for q in queries:\r\n",
    "            if q > mx:\r\n",
    "                ans.append(-1)\r\n",
    "            else:\r\n",
    "                dfs(0, q)\r\n",
    "                ans.append(int(res))\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\r\n",
    "        if intLength == 1:\r\n",
    "            return  [q if q <= 9 else -1 for q in queries]\r\n",
    "        path = [\"\"] * intLength\r\n",
    "        def dfs(i:int, left: int) -> int :\r\n",
    "            if i == (intLength - 1) // 2  + 1 :\r\n",
    "                return  int(\"\".join(path))       \r\n",
    "            cnt = pow(10, (intLength + 1) // 2 - i - 1)\r\n",
    "            low = 1 if i == 0 else 0\r\n",
    "            for x in range(low, 10):\r\n",
    "                if left - cnt > 0:\r\n",
    "                    left -= cnt\r\n",
    "                else:\r\n",
    "                    path[i] = path[len(path) - i - 1] = str(x)\r\n",
    "                    return dfs(i + 1, left)\r\n",
    "                \r\n",
    "        mx = pow(10, (intLength + 1) // 2 - 1) * 9\r\n",
    "        return [-1 if q > mx else dfs(0, q) for q in queries]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        one = [str(i) for i in range(0, 10)]\n",
    "\n",
    "        def f(x, intLength):\n",
    "            if intLength == 1:\n",
    "                return one[x]\n",
    "            if intLength % 2 == 0:\n",
    "                s = f(x, intLength - 1)\n",
    "                mid = len(s) // 2\n",
    "                return s[:mid] + s[mid] + s[mid:]\n",
    "            else:\n",
    "                int_, dec_ = (x-1)// 10+1 if intLength>=3 else (x-1)// 10, x % 10\n",
    "                s = f(int_, intLength - 1)\n",
    "                mid = len(s) // 2\n",
    "                return s[:mid] + one[dec_-1] + s[mid:]\n",
    "        result = []\n",
    "        max_ = 9*10**((intLength-1)//2)\n",
    "        for i in queries:\n",
    "            if i>max_:\n",
    "                result.append(-1)\n",
    "            else:\n",
    "                result.append(int(f(i,intLength)))\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        k = (intLength + 1 )// 2\n",
    "        half = []\n",
    "\n",
    "        for q in queries:\n",
    "            start = 10 ** (k - 1)\n",
    "            end = 10 ** k - 1\n",
    "            maxq = end - start + 1\n",
    "            if q > maxq:\n",
    "                half.append(-1)\n",
    "            else:\n",
    "                half.append(start + q - 1)\n",
    "        \n",
    "        ans = []\n",
    "        # 偶数情况\n",
    "\n",
    "        if intLength % 2 == 0:\n",
    "            ans = [int(str(item) + str(item)[::-1]) if item != -1 else -1 for item in half]\n",
    "        else:\n",
    "            ans = [int(str(item) + str(item)[:-1][::-1]) if item != -1 else -1 for item in half]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        k = (intLength + 1 )// 2\n",
    "        half = []\n",
    "\n",
    "        for q in queries:\n",
    "            start = 10 ** (k - 1)\n",
    "            end = 10 ** k - 1\n",
    "            maxq = end - start + 1\n",
    "            if q > maxq:\n",
    "                half.append(-1)\n",
    "            else:\n",
    "                half.append(start + q - 1)\n",
    "        \n",
    "        ans = []\n",
    "        # 偶数情况\n",
    "        print(half)\n",
    "        if intLength % 2 == 0:\n",
    "            ans = [int(str(item) + str(item)[::-1]) if item != -1 else -1 for item in half]\n",
    "        else:\n",
    "            ans = [int(str(item) + str(item)[:-1][::-1]) if item != -1 else -1 for item in half]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        halfIntLength = (intLength + 1) // 2\n",
    "        countPalindrome = 9 * 10 ** (halfIntLength-1)\n",
    "        res = []\n",
    "        for num in queries:\n",
    "            if num > countPalindrome:\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                u = num - 1\n",
    "                digits = []\n",
    "                for _ in range(halfIntLength):\n",
    "                    u, v = divmod(u, 10)\n",
    "                    digits.append(v)\n",
    "                digits[-1] += 1\n",
    "                fullDigits = digits[:]\n",
    "                fullDigits.reverse()\n",
    "                if intLength%2:\n",
    "                    fullDigits.pop()\n",
    "                fullDigits += digits\n",
    "                u = 0\n",
    "                for digit in fullDigits:\n",
    "                    u *= 10\n",
    "                    u += digit\n",
    "                res.append(u)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:\n",
    "        def numToPalindrome(num, intLength):\n",
    "            assert int(math.log10(num))+1 == (intLength+1)//2\n",
    "            ans = num\n",
    "            walk = num if intLength%2 == 0 else num//10\n",
    "            while walk > 0:\n",
    "                new_digit = walk % 10\n",
    "                ans = ans * 10 + new_digit\n",
    "                walk = walk // 10\n",
    "            return ans\n",
    "        \n",
    "        numLength = (intLength+1)//2\n",
    "        minNum = 10**(numLength-1)\n",
    "        numAvailable = 9*(10**(numLength-1))\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            if query > numAvailable:\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(numToPalindrome(minNum + query - 1, intLength))\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
